import com.sun.deploy.panel.TreeBuilder;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-10-11
 * Time: 8:33
 */
public class TestBinaryTree {
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode(char val){
            this.val = val;
        }
    }
    private int i = 0;
    public TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    // 获取树中节点的个数
    int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k){
        if(root == null || k <=0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+ getKLevelNodeCount(root.right,k-1);

    }
    // 获取二叉树的高度
    int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        return getHeight(root.left) > getHeight(root.right) ? getHeight(root.left)+1: getHeight(root.right)+1;
    }
    // 检测值为value的元素是否存在
    Boolean find(TreeNode root, int val){
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }
        Boolean ret1 = find(root.left,val);
        if(ret1 != false){
            return true;
        }
       Boolean ret2 = find(root.right,val);
            if(ret2 != false){
                return true;
            }
        return false;
    }
    //层序遍历
    void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null){
                qu.offer(cur.left);
            }
            if(cur.right != null){
                qu.offer(cur.right);
            }
        }
    }
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.poll();
            if(cur != null){
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else {
                break;
            }
        }
        while (!qu.isEmpty()){
            TreeNode ret = qu.poll();
            if(ret != null){
                return false;
            }
        }
        return true;
    }
}
